講義概要/Class Outline

ソフトウェアとは、プログラミング言語を用いてアルゴリズムを実装したものである。ソフトウェアの性能を評価する指標の一つとして、処理時間が重要である。実際にプログラムを作成して実行してみれば、どの程度の処理時間が必要かは判明する。しかしながらプログラムを作成する前に、アルゴリズムを対象に解析を行うことで漸近的な性能を把握することが出来れば、ソフトウェアの性能に対する予測ができる。本講義ならびに引き続き実施されるアルゴリズム論IIにおいては、実行時間の解析によりアルゴリズムの性能評価を行う方法を理解することを目的とする。本講義では、比較的易しい問題とアルゴリズムを対象とし、アルゴリズム評価のために必要な基礎的な事項を理解することが目標である。  

講義計画 /Class Structure

回	内容
1	講義概要 講義概要と計画について説明する。
2	問題とアルゴリズム 処理対象を厳密に定式化することの重要性とアルゴリズム、プログラムとの関連を解説する。
3	簡単なアルゴリズム（１） 変数と代入、return 文だけで構築できるアルゴリズムを取りあげ、擬似コードと RAMモデルを導入する。
4	簡単なアルゴリズム（２） 変数と代入、return 文だけで構築できるアルゴリズムを取り上げ、実行時間の解析の初歩を学ぶ。
5	簡単なアルゴリズム（３） 加算と減算を用いたアルゴリズムを取り上げ、実行時間の解析の初歩を学ぶ。
6	簡単なアルゴリズム（４） 乗算、除算などの演算を用いたアルゴリズムを取り上げ、実行時間の解析の初歩を学ぶ。
7	小テスト１ 第６回までの内容についてテストを行う。
8	補足と復習 テストの解説ならびに補足と復習を行う。
9	条件分岐のあるアルゴリズムと最悪実行時間 条件分岐のあるアルゴリズムを取り上げ、最悪計算時間の解析の初歩を学ぶ
10	条件分岐のあるアルゴリズムと平均実行時間（１） 条件分岐のあるアルゴリズムを取り上げ、平均実行時間の解析の初歩を学ぶ。
11	条件分岐のあるアルゴリズムと平均実行時間（２） ひきつづき条件分岐のあるアルゴリズムを取り上げ、平均実行時間の解析の初歩を学ぶ。
12	最悪実行時間と平均実行時間 最悪実行時間と平均実行時間を比較することを通し、それぞれの概念に対する理解を深める。
13	小テスト２ 第８回から第１２回の内容についてテストを行う。
14	補足と復習 テストの解説ならびに補足と復習を行う。